package com.captain.special.链表;

import com.captain.leetcode.链表.ListNode;

import java.util.List;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/3/28 9:17
 */
public class 两数相加2445 {
    public static void main(String[] args) {
        new 两数相加2445().addTwoNumbers(ListNode.getInstance(), ListNode.getInstance1());
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        //将链表进行翻转计算
        ListNode flipL1 = flip(l1);
        ListNode flipL2 = flip(l2);
        //两数相加
        //最后将结果进行翻转
        return flip(doAddTwoNumbers(flipL1, flipL2));
    }

    public ListNode doAddTwoNumbers(ListNode l1, ListNode l2) {
        //最后的进位
        int carry = 0;
        //1.遍历两个链表
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            int l1Val = l1.val;
            int l2Val = l2.val;
            int sum = l1Val + l2Val + carry;
            //取模为当前余数
            int curVal = sum % 10;
            cur.next = new ListNode(curVal);
            cur = cur.next;
            l1 = l1.next;
            l2 = l2.next;
            carry = sum / 10;
        }

        if (l1 != null) {
            while (l1 != null) {
                int l1Val = l1.val;
                int sum = l1Val + carry;
                int curVal = sum % 10;
                cur.next = new ListNode(curVal);
                cur = cur.next;
                carry = sum / 10;
                l1 = l1.next;
            }
        } else if (l2 != null) {
            while (l2 != null) {
                int l2Val = l2.val;
                int sum = l2Val + carry;
                int curVal = sum % 10;
                cur.next = new ListNode(curVal);
                cur = cur.next;
                carry = sum / 10;
                l2 = l2.next;
            }
        }
        if (carry != 0) {
            cur.next = new ListNode(carry);
        }
        return dummy.next;
    }

    public ListNode flip(ListNode head) {
        //链表翻转
        //1234
        ListNode pre = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}
